This application is being filed with a microfiche appendix of computer program listings consisting of one (1) fiche having 40 frames.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates to halftoning by error diffusion, enhanced so as to reduce the presence of structural artifacts in the halftoned output while avoiding an artificial increase in halftoning image noise. Specifically, error diffusion according to the invention divides the input gray level intensity range into different segments for purposes of both thresholding and error diffusion. Different error diffusion threshold masks are applied for each respective segment, and different error diffusion weights are applied for each respective segment, with a decision being made as to whether or not to apply a different threshold mask being based on the local image gradient of the image.
2. Description of the Related Art
Error diffusion halftoning, as generally described in the seminal works by Floyd, Steinberg and Stucki, has become one of the most popular techniques for producing halftoned image output based on a continuous tone image input. Particularly in connection with computerized images, where each input pixel is represented by multi-level data such as an 8-bit gray scale or 24-bit color value, error diffusion halftoning has been found to yield pleasing results in images printed with binary or limited level output printers such as color ink jet printers and the like. Error diffusion tends to enhance edge sharpness and further tends to preserve fine image detail while yielding an overall pleasing image.
Generally speaking, error diffusion proceeds in accordance with the following steps. First, a pixel in the continuous tone image is compared against a threshold (or ranges of thresholds for an output device with several levels) so as to determine what output value should be printed by the image output device. For example, in the case of a binary printer (meaning a printer that outputs at each pixel either a dot or an absence of a dot), the threshold may be ½ of the intensity range, with a pixel being printed if the continuous tone value exceeds ½ and with no pixel being printed if the continuous tone value does not exceed ½. Then, the error between the continuous tone input and the actual output value is calculated. This error is diffused to adjacent pixels using predetermined weighting coefficients, so that predesignated proportions of the error are added to the original image value of adjacent pixels. Processing then proceeds with another pixel in a predetermined scan direction. When it comes time to threshold one of the adjacent pixels so as to determine whether or not to print a dot, the determination is based on the original value plus any accumulated errors.
Because of the exceedingly good image output obtained from error diffusion halftoning, a tremendous amount of effort has been expended on variations of the basic Floyd Stucki Steinberg technique so as to yield images of improved quality. Thus, various researchers have proposed changes to thresholding, changes to error diffusion coefficients, and changes in scan patterns, so as to improve error diffusion output.
Despite the amount of research aimed at error diffusion, there are several lingering problems. One of these problems concerns the formation of artifacts in the halftoned output. These artifacts form when error diffusion leads to repetitive output. Repetitive output can cause worm-like structural artifacts to appear in the halftoned output, particularly in areas of highlights such as extremely light or dark areas of an image. FIG. 1, for example, is the output 10 from conventional error diffusion halftoning, for each of 24 gray patches representing the first 24 out of 256 continuous tone gray levels. As seen in FIG. 1 at extremely light gray level highlights, repetitive output has caused worm-like artifacts such as those at 11 and 12.
Repetitive output can also cause regular patterns such as a checkerboard pattern to appear in the output. For example, FIG. 2 is the output of conventional error diffusion halftoning for a continuous tone gray wedge that varies from full dark gray (or black) to full light gray (or white). As seen at 50% gray, the halftoned output 16 has a regularized checkerboard artifact caused by repetitive output. The same artifact can be seen to a lesser degree at 25% gray and 75% gray.
Both kinds of structural artifacts are visually distracting and detract from the overall quality of the image. Moreover, in connection with color printing, the existence of regular patterns such as a checkerboard pattern can, when color components are overlaid, result in severe color shifts which manifest themselves as discolored halos of color around solid or gradually varying color regions. These structural artifacts manifest themselves in particularly displeasing ways at intensity values corresponding to integral fractions of the intensity range. Thus, a severe structural artifact is created at a intensity value of ½ (i.e., 50% gray), with structural artifacts of lesser visibility being observed at ⅓, ⅔, ¼, ¾, ⅕, ⅖, ⅗, etc. (i.e., integral fractions) of the intensity range.
The inventor of this application has previously proposed one technique for reducing the existence of artifacts. Thus, in U.S. Pat. No. 5,737,453, “Enhanced Error-Diffusion Method For Color Or Black-And-White Reproduction”, the inventor herein proposed a technique for reducing halftoning artifacts by adjusting the threshold used in the halftoning decision, and by adjusting the coefficients of weights used to diffuse error. The technique described therein produced significantly reduced structural artifacts through a process that can inaccurately be conceptualized as introducing noise into the thresholding and the error diffusion process.